/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/* 
 * File:   list.h
 * Author: bluce
 *
 * Created on 2021年2月28日, 下午12:24
 */

#ifndef LIST_H
#define LIST_H

#include <stddef.h>

#ifdef __cplusplus
extern "C" {
#endif

struct list_head{
	struct list_head *next, *prev;
};

typedef struct list_head queue_t;
    
#define LIST_HEAD_INIT(name)    \
{                               \
    &(name),                    \
    &(name),                    \
}

#ifndef offsetof   
#define offsetof(TYPE, MEMBER)  ((size_t) &((TYPE *)0)->MEMBER)
#endif
    
#define container_of(ptr, type, member) ({          \
    const typeof( ((type *)0)->member) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type, member) );})
    
/**
 * list_entry - get the struct for this entry.
 * @ptr:      the &struct list_head pointer.
 * @type:     the type of the struct this is embedded in.
 * @member:   the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member)   container_of(ptr, type, member)
    
#define LIST_HEAD(name)         \
    struct list_head name = LIST_HEAD_INIT(name)
    
static inline void INIT_LIST_HEAD(struct list_head *list){
    list->next = list;
    list->prev = list;
}

static inline void __list_add(struct list_head *new_,
        struct list_head *prev,
        struct list_head *next){
    next->prev = new_;
    new_->next = next;
    new_->prev = prev;
    prev->next = new_;
}

static inline void list_add(struct list_head *new_, 
        struct list_head *head){
    __list_add(new_, head, head->next);
}

/**
 * list_add_tail - add a new entry
 * @new_: new entry to be added.
 * @head: list head to add it before.
 * 
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new_, 
        struct list_head *head){
    __list_add(new_, head->prev, head);
}

#define list_for_each(pos, head)                        \
    for(pos = (head)->next; pos != (head); pos = pos->next)

/**
 * list_for_each_entry - iterate over list of given type.
 * @pos:      the type * to use as a loop cursor.
 * @head:     the head of your list.
 * @member:   the name of the list_struct within the struct.
 */
#define list_for_each_entry(pos, head, member)          \
    for(pos = list_entry((head)->next, typeof(*pos), member);   \
    prefetch(pos->member.next), &pos->member != (head);         \
    pos = list_entry(pos->member.next, typeof(*pos), member))

/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 * 
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head *prev, 
        struct list_head *next){
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry){
    __list_del(entry->prev, entry->next);
    entry->next = NULL;
    entry->prev = NULL;
}

/**
 * list_for_each_entry_safe - iterate over list of given type safe against 
 * removal of list enty.
 * @pos:      the type * to use as a loop sursor.
 * @n:        another type * to use as temporary storage.
 * @head:     the head for your list.
 * @member:   the name of the list_struct within the strut.
 */
#define list_for_each_entry_safe(pos, n, head, member)      		\
    for (pos = list_entry((head)->next, typeof(*pos), member),      \
         n = list_entry(pos->member.next, typeof(*pos), member); 	\
         &pos->member != (head);                                    \
         pos = n, n = list_entry(n->member.next, typeof(*n), member))

/**
 * list_del_init - deletes entry from list and reinitialize it.
 * @entry: the element to delete from the list.
 */
static inline void list_del_init(struct list_head *entry){
    __list_del(entry->prev, entry->next);
    INIT_LIST_HEAD(entry);
}

/**
 * list_replace - replace old entry by new one
 * @old:  the element to be replaced.
 * @new_: the new element to insert.
 * 
 * If @old was enmpty, it will be overwritten.
 */
static inline void list_replace(struct list_head *old,
        struct list_head *new_){
    new_->next = old->next;
    new_->next->prev = new_;
    new_->prev = old->prev;
    new_->prev->next = new_;
}

static inline void list_replace_init(struct list_head *old,
        struct list_head *new_){
    list_replace(old, new_);
    INIT_LIST_HEAD(old);
}

/**
 * list_move - delete from one list and add as another's head.
 * @list: the entry to move.
 * @head: the head that will precede our entry.
 */
static inline void list_move(struct list_head *list,
        struct list_head *head){
    __list_del(list->prev, list->next);
    list_add(list, head);
}

/**
 * list_move_tail - delete from one list and add as another's tail.
 * @list:  the entry to move.
 * @head:  the head that will follow our entry.
 */
static inline void list_move_tail(struct list_head *list,
        struct list_head *head){
    __list_del(list->prev, list->next);
    list_add_tail(list, head);
}

/**
 * list_for_each_entry_reverse - iterate backwards over list of given type.
 * @pos:     the type * to use as a loop cursor.
 * @head:    the head for your list.
 * @member:  the name of the list_struct within the struct.
 */
#define list_for_each_entry_reverse(pos, head, member)      \
    for(pos = list_entry((head)->prev, typeof(*pos), member);\
    prefetch(pos->member.prev), &pos->member != (head);      \
    pos = list_entry(pos->member.prev, typeof(*pos), member))

/**
 * list_for_each_entry_safe_reverse
 * @pos:      the type *  to use as a loop cursor.
 * @n         another type * to use as temporary storage.
 * @head:     the head for your list.
 * @member:   the name of the list_struct within the struct.
 * 
 * Iterate backwards over list of given type, safe against removal
 * of list entry.
 */
#define list_for_each_entry_safe_reverse(pos, n, head,member)       \
    for(pos = list_entry((head)->prev, typeof(*pos), member),   \
    n = list_entry(pos->member.prev, typeof(*pos), member);     \
    &pos->member != (head);                                     \
    pos = n, n = list_entry(n->member.prev, typeof(*n), member))

/**
 * list_first_entry - get the first element from a list.
 * @ptr:     the list head to take the element from.
 * @type:    the type of the struct this is embedded in.
 * @member:  the name of the list_struct within the struct.
 * 
 * Note, that list is expected to be not empty.
 */
#define list_first_entry(ptr, type, member) \
    list_entry((ptr)->next, type, member)

/**
 * list_is_last - tests whether @list is the last entry in list @head
 * @list: the entry to test.
 * @head: the head of the list.
 */
static inline int list_is_last(const struct list_head *list,
        const struct list_head *head){
    return list->next == head;
}

/**
 * list_empty - tests whether a list is empty.
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head){
    return head->next == head;
}

/**
 * 在列表中升序插入，值更小的靠近链表头
 */
#define list_ascending_order_add(new_, pos, n, head, member, condition_member) 	\
do{ 																			\
	if(!list_empty(head)) 														\
    { 																			\
        list_for_each_entry_safe(pos, n, head, member) 							\
        { 																		\
            if(pos->condition_member > new_->condition_member) 					\
            { 																	\
                list_add_tail(&new_->member, &pos->member); 					\
                break; 															\
            } 																	\
        } 																		\
    } 																			\
    /* 如果节点没有被插入队列，则empty检查为空，前提是对节点进行初始化 */ 		\
    if(list_empty(&new_->member)) 												\
    { 																			\
        list_add_tail(&new_->member, head); 									\
    } 																			\
}while(0)

#define queue_empty(queue)	list_empty((struct list_head *)&queue)

#define queue_push(new_, head) 	list_add_tail((struct list_head *)&new_, (struct list_head *)&head)
	
static inline queue_t *_queue_pop(queue_t *head){
	queue_t *ret = head->next;
	list_del(ret);
	return ret;
}

#define queue_pop(ptr, type, member)	list_entry(_queue_pop(ptr), type, member)


#ifdef __cplusplus
}
#endif

#endif /* LIST_H */

